package com.zhanghp.class031;

/**
 * 返回n的二进制中有几个1
 * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
 * 给你两个整数 x 和 y，计算并返回它们之间的汉明距离
 * 测试链接 : https://leetcode.cn/problems/hamming-distance/
 *
 * @author zhanghp
 * @since 2024/4/8 15:25
 */
public class Code06_CountOnesBinarySystem {

    static class Solution {
        public int hammingDistance(int x, int y) {
            // 算他俩个数不同位有几个，相当于0,1不同的为一次，异或下就可得到一个数
            return cntOnes(x ^ y);
        }

        /**
         * <p>
         * 算步长为1，有几个1
         * 再算步长为2，有几个1
         * 再算步长为4，有几个1
         * ...
         * </p>
         * <p>
         * 比如步长为1时，先看个位有1没，然后再看十位有1没，然后相加
         * <br/>
         * 举例：11_01_10_11  <br/>
         * 11_01_10_11 <br/>
         * & 01 01 01 01 <br/>
         * 0101_0001  这样得出步长为1 个位数的1的个数<br/>
         * <hr/>
         * 11_01_10_11 <br/>
         * >>> 1
         * 01_10_11_01 <br/>
         * & 01 01 01 01 <br/>
         * 01 00 01 01 得出步长为1 十位数上的1的个数<br/>
         * <hr/>
         * 个位得到1的数，和十位得到1的个数相加<br/>
         * 0101_0001 <br/>
         * + 0100_0101 <br/>
         * 1001_0110 <br/>
         * <hr/>
         * 原来             11_01_10_11<br/>
         * 结果             10_01_01_10<br/>
         * 1的个数（step为1）   2  1  1  2<br/>
         * </p>
         *
         * @param n
         * @return
         */
        public int cntOnes(int n) {
            n = (n & 0x5555_5555) + ((n >>> 1) & 0x5555_5555);
            n = (n & 0x3333_3333) + ((n >>> 2) & 0x3333_3333);
            n = (n & 0x0f0f_0f0f) + ((n >>> 4) & 0x0f0f_0f0f);
            n = (n & 0x00ff_00ff) + ((n >>> 8) & 0x00ff_00ff);
            n = (n & 0x0000_ffff) + ((n >>> 16) & 0x0000_ffff);
            return n;
        }
    }
}
